package 归并;

import 其他.DataStructure.TreeNode;
import org.junit.Test;

/*
    做完题一定写入表格
*/
public class 中序前序_字符串构造二叉树105 {
    @Test
    public void test() {
        int[] pre = {1,2}, zhong={2,1};
        buildTree(pre,zhong);
    }

    //q前序 z中序
    int[] q,z;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        q=preorder;z=inorder;
        int qL=0,qR=q.length-1,zL=0,zR=z.length-1;
        return back(qL,qR,zL,zR);
    }
    private TreeNode back(int qL, int qR, int zL, int zR) {
        if(
                //0n都要封住，因为+1-1都有
                qL<0||qL>=q.length ||
                zL<0||zL>=z.length ||
                qR<0||qR>=q.length ||
                zR<0||zR>=z.length ||
                //这个要背
                qL>qR || zL>zR
        ){
            //return null没事，我叶子9的时候不连它就行
            return null;
        }
        //前序剩一个 叶子9
        if(qL==qR){
            return new TreeNode(q[qL]);
        }

        //盯住一个方框+双闭区间(每次删m)+0用L,n用R代替，就不会乱
        //向下找m
        int rotVal = q[qL];
        int z_ind = return_zhongxuInd_findValInZhongxu(zL,zR,rotVal);
        int left_next_zL = zL, left_next_zR = z_ind-1;
        int right_next_zL = z_ind+1, right_next_zR = zR;
        //向上拆
        int left_next_qL = qL+1, left_next_qR = qL+z_ind-zL;
        int right_next_qL = left_next_qR+1, right_next_qR = qR;

        //rot指向中序序列中的某个节点
        TreeNode rot = new TreeNode(rotVal);
        rot.left = back(left_next_qL,left_next_qR,left_next_zL,left_next_zR);
        rot.right = back(right_next_qL,right_next_qR,right_next_zL,right_next_zR);
        return rot;
    }
    private int return_zhongxuInd_findValInZhongxu(int zL, int zR, int rotVal) {
        for (int i = zL; i <= zR; i++) {
            if(z[i]==rotVal){
                return i;
            }
        }
        return -1;
    }
}
